package getIntersectionNode;

import java.util.HashSet;
import java.util.Set;

public class Solution {
    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//        Set<ListNode> set = new HashSet<>();
//        ListNode p = headA;
//        while (p!=null) {
//            set.add(p);
//            p = p.next;
//        }
//        p = headB;
//        while (p!=null) {
//            if(set.contains(p)) return p;
//            p = p.next;
//        }
//        return null;


        // 双指针
        // 如果有交点的话
        // 从交点开始到结束 长度是一致的
        // 即交点 p = m-k
        //       p = n-k

        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1!=p2) {
            p1 = p1 == null?headB:p1.next;
            p2 = p2 == null?headA:p2.next;
        }
        return p1;
    }
}
